Sipser CH2 PROBLEMS'ANSWER 2.33-2.42

Zhao Cong

2.33

考虑pumping length为 ,对字符应用pumping lemma.

  1. 对情况1:只在里,

    • 对于,
    • ,字符为
    • 已知,只需
    • 因为,,不可能整除比自己小的数
    • 矛盾,此情况不成立
  2. 对情况2: only consists of b

    • ,
    • ,Consider and
    • ,
    • ,不可能整除
    • Contradiction.
  3. For 3 : in the boundary of and

    • ,
    • 如果,则
    • ,退化至情况1
    • ,,
    • ,,
    • ,
    • ,
    • Contradiction

结论:F is not CFL

2.34

  • ,验证不成立
  • ,
    • 验证时,,
    • 验证时,,
    • 成立

2.35

  • 设派生树的高度为,至多有个叶子结点,生成的字符长度,对于的CNF文法生成的派生树有
  • 设派生出长度为的字符需要步,,
  • ,是整数,
  • ,,
  • 高度为的树至少有个变量,必定有变量重复一次
  • 仿照泵引理证明,我们有三种规则
  • 反复利用规则2造出无限集合

2.36

2.37

  • 思路为选取合适的泵长度,使解析树的高度至少为,导致至少有一个变量的三次重复。满足条件a
  • 详情见Gemini的回答
  • 说实话条件b,c没看懂

2.38

  • 考虑CFL,,,perfect shuffle为
  • 应用pumping lemma易验证 is not CFL

2.39

  • 考虑CFL,,
  • Regular Language,
  • is 's shuffle,
  • 应用pumping lemma易验证 is not CFL
  • is not CFL

2.40

  • is infinite,Prefix-closed CFL.
  • Use Pumping Lemma: is an infinite subset of ,
    • ,a prefix of is , is infinite and regular
    • ,a prefix of is , is infinite and regular
  • contains an infinite regular subset

2.41

  • For :
      • 该运算意为字符去掉任何后缀不能在L中,故舍去
      • 时可能成为的前缀,舍去
    • 应用泵引理易验证 is not CFL
  • For 同理,意为添加任何后缀不能在L中

2.42

考虑,应用泵引理易验证

On this page
Sipser CH2 PROBLEMS'ANSWER 2.33-2.42